from typing import List, Tuple
import ipaddress
from itertools import permutations

class NetworkValidator:
    def __init__(self, network_prefix: str):
        """初始化网络验证器"""
        self.network = ipaddress.ip_network(network_prefix)
        self.subnets = []  # 存储所有子网
        
    def add_subnet(self, name: str, hosts: int) -> None:
        """添加子网"""
        # 计算所需的网络位数（向上取整到最近的2的幂）
        subnet_size = 1
        while subnet_size - 2 < hosts:  # 减2是因为网络地址和广播地址
            subnet_size *= 2
        bits = 32 - subnet_size.bit_length()
        self.subnets.append((name, hosts, bits, subnet_size))
        
    def generate_all_allocations(self) -> List[List[str]]:
        """生成所有可能的IP地址分配方案"""
        # 首先检查总地址需求
        total_addresses = sum(size for _, _, _, size in self.subnets)
        if total_addresses > self.network.num_addresses:
            print(f"总需求({total_addresses})超过可用地址数({self.network.num_addresses})")
            return []
            
        # 生成所有可能的子网排列
        all_allocations = []
        for subnet_order in permutations(range(len(self.subnets))):
            current_ip = int(self.network.network_address)
            allocation = []
            valid = True
            
            for idx in subnet_order:
                name, hosts, bits, subnet_size = self.subnets[idx]
                # 确保子网边界对齐
                mask = (1 << (32 - bits)) - 1
                aligned_ip = (current_ip + mask) & ~mask
                
                if aligned_ip + subnet_size > int(self.network.broadcast_address):
                    valid = False
                    break
                    
                subnet = ipaddress.ip_network(f"{ipaddress.IPv4Address(aligned_ip)}/{bits}")
                allocation.append(f"{name}: {subnet} (可用主机数: {subnet_size-2})")
                current_ip = aligned_ip + subnet_size
                
            if valid:
                all_allocations.append(allocation)
                
        return all_allocations

def main():
    # 创建验证器
    validator = NetworkValidator('192.77.33.0/24')
    
    # 添加所有子网
    subnets = [
        ('LAN1', 50),  # 需要64个地址 (/26)
        ('LAN2', 10),  # 需要16个地址 (/28)
        ('LAN3', 30),  # 需要32个地址 (/27)
        ('LAN4', 10),  # 需要16个地址 (/28)
        ('LAN5', 2),   # 需要4个地址  (/30)
        ('WAN1', 2),   # 需要4个地址  (/30)
        ('WAN2', 2),   # 需要4个地址  (/30)
        ('WAN3', 2),   # 需要4个地址  (/30)
    ]
    
    for name, hosts in subnets:
        validator.add_subnet(name, hosts)
    
    # 生成所有可能的分配方案
    all_allocations = validator.generate_all_allocations()
    
    # 打印结果
    print(f"共找到 {len(all_allocations)} 种可行的分配方案")
    print("=" * 50)
    
    # 只打印前5种方案
    for i, allocation in enumerate(all_allocations[:5], 1):
        print(f"\n方案 {i}:")
        for subnet in allocation:
            print(subnet)
        print("-" * 50)
        
    if len(all_allocations) > 5:
        print(f"\n... 还有 {len(all_allocations) - 5} 种方案未显示")

if __name__ == "__main__":
    main()
